package ch04;
//判断是否是二分图
public class TwoColor {
    private boolean[] marked;
    private boolean[] color;
    private boolean isTwoColor = true;

    public TwoColor(Graph graph) {
        color = new boolean[graph.V()];
        marked = new boolean[graph.V()];
        for (int i = 0; i < graph.V(); i++) {
            if (!marked[i]) {
                DFS(graph, i);
            }
        }
    }

    public void DFS(Graph graph, int v) {

        marked[v] = true;

        for (Integer w : graph.adj(v)) {
            if (!marked[w]) {
                color[w] = !color[v];
                DFS(graph, w);

            }else{
                if(color[w]==color[v])
                    isTwoColor = false;
            }
        }
    }

    public boolean isTwoColor(){
        return isTwoColor;
    }

    public static void main(String[] args) {
        TwoColor twoColor = new TwoColor(Graph.getGraphUseCase());
        System.out.println(twoColor.isTwoColor());
    }
}
